/*
题目 : 统计特殊整数
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

https://leetcode.cn/problems/count-special-integers/
 */
public class CountSpecialNumbers {
    char[] cs = null;
    int size ;
    public int countSpecialNumbers(int n) {
        cs = String.valueOf(n).toCharArray();
        size = cs.length;
        int[][] memo = new int[size][1 << 10]; // 最高位下标为 1 ; 下标为 i , 状态为 j 的时候个数, 记忆化

        for (int i = 0; i < size; i ++) {
            Arrays.fill(memo[i], -1);  // -1 表示没有更新过
        }

        return dfs(memo, 0, 0, true, false);
    }

    // 记忆化数组, 防止对同一过程进行重复运算, pos : 当前下标,  limited : 当前是否受限, hasNum 表示前面有没有有效数字
    private int dfs(int[][] memo, int pos, int mark, boolean limited, boolean hasNum) {
        // 完成一条路径, 返回 1
        if (pos >= size) {
            return hasNum ? 1 : 0;
        }
        int src = 0;

        // 如果不受限, 并且前面有数字, (受限的过程在整个递归中只会发生一次)
        if (!limited && hasNum && memo[pos][mark] != -1) {
            return memo[pos][mark]; // 5  3  2  x  x  和  2  5  3  x  后面的选择都是一样的
        }

        // 如果没有填数字, 这里也可以不填
        if (!hasNum) {
            // 需不需要 src += ?, 进入这里, 那么 memo 就不会更新为 src, 需要统计总个数
            src += dfs(memo, pos + 1, mark, false, false);
        }

        // 有数字就 从 0 开始, 没有就从 1 开始
        int up = limited ? cs[pos] - '0' : 9;
        for (int i = hasNum ? 0 : 1 ; i <= up; i ++) {
            if (((mark >> i) & 1) == 0) { // 这位数字还没有用过
                //                                           要受限需要前面那个受限, 后面这个也受限
                src += dfs(memo, pos + 1, mark | (1 << i), limited && i == (cs[pos] - '0'), true); // 填了数字说明就有数字了
            }
        }

        // 不受限并且 前面有数字 就更新 memo 
        if (!limited && hasNum) {
            memo[pos][mark] = src;
        }
        return src;
    }
    // 7  8   9  5    5

    // 前三位状态一样, 没有limit, 也没有 hasNum
    // 5   2    3|   8   1
    // 5   3    2|   5    5
    // 即可以直接使用记忆化搜索的结果

    // 有前置 0

    // 0   5  2  3|  5  这个结果不能使用,  到第 4 为 mask 值 也是一样的, 但是直接使用结果是不对的

    // 有限制的情况下, 在递归过程中只会出现一次, 没有必要进行记录
    // 7
    // 7   8
}
